#include <bits/stdc++.h>
using namespace std;

// 对叶枫的https://www.acwing.com/solution/content/5158/
// 进行个人风格的修改，以便理解
const int INF = 0x01010101;
int g[15][15], mdst[15], n, m,
    ans = INF;  // g:图的连接表,mdst:每个点最小的连接距离
int lay[15][15], nlay[15];  // lay:每层第i个是哪个点,nlay:每层多少个点
bool used[15];              //每个点是否被用过

// 返回值无用，但方便编程，
// 现在第ceng层，讨论结点k，总共用了cnt个点，现在这棵树价值sum，剩余点的总最小距离rem
int dfs(int ceng, int k, int cnt, int sum, int rem) {
  //最优性剪枝
  //！！！最重要！！！只要现阶段不是最小的了就没有继续的必要了
  if (sum + rem * ceng >= ans) return 0;
  //上一层没有选入点（上层为空），树不可能继续构建，该可能不合法，直接跳过
  if (nlay[ceng - 1] == 0) return 0;
  //所有点都已经被构建进树中，更新答案，结束这种可能
  if (cnt == n) return ans = min(sum, ans);
  //该层所有点都讨论过一遍，继续下一层
  if (k > n) return dfs(ceng + 1, 1, cnt, sum, rem);
  //该点已用，直接讨论下一个点
  if (used[k] == 1) return dfs(ceng, k + 1, cnt, sum, rem);

  used[k] = 1;     //能算到这里，该点没用过，用下试试
  int mini = INF;  //找到该点与上层的最小联系
  //若与上层所有点不连通，则mini是INF,会被最优性剪枝减去
  for (int i = 1; i <= nlay[ceng - 1]; i++)
    mini = min(mini, g[k][lay[ceng - 1][i]]);
  nlay[ceng]++;               //这层又多一个点啦
  lay[ceng][nlay[ceng]] = k;  //这点是哪个？存在 lay[哪层][第几个] 中

  // 选用此点（可能1）
  dfs(ceng, k + 1, cnt + 1, sum + mini * ceng, rem - mdst[k]);

  nlay[ceng]--;  // 恢复数据，以备下一个dfs

  // 不用此点（可能2）
  used[k] = 0;
  return dfs(ceng, k + 1, cnt, sum, rem);
}
int main() {
  cin >> n >> m;
  //数组初始化,每个都=0x01010101，不能用0x3f，参与运算会overflow
  memset(g, 1, sizeof g);
  memset(mdst, 1, sizeof mdst);

  for (int i = 1; i <= m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b) continue;
    g[a][b] = g[b][a] = min(g[a][b], c);  //无向图双向赋值，只取最小值
    mdst[a] = min(mdst[a], c), mdst[b] = min(mdst[b], c);
  }
  int sum = 0;
  for (int i = 1; i <= n; i++) sum += mdst[i];
  for (int i = 1; i <= n; i++) {     // 每个点都当一次根
    used[i] = 1;                     // 点已用
    lay[0][1] = i;                   // 根看做第0层
    nlay[0] = 1;                     // 0层有一个根节点
    dfs(1, 1, 1, 0, sum - mdst[i]);  // 从第一层开始搜索
    used[i] = 0;                     // 以该点为根的数搜索完毕
  }
  cout << ans;
  return 0;
}

// 作者：b507jiang 链接：https
// www.acwing.com/solution/content/55342/
// 来源：AcWing
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
